package com.cuz.hot100;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class Q17phoneNumberLetterCombination {
    public static void main(String[] args) {

        System.out.println(letterCombinations1("23"));


    }

    static HashMap<Character, String> map = new HashMap<>();

    static {
        map.put('2', "abc");
        map.put('3', "def");
        map.put('4', "ghi");
        map.put('5', "jkl");
        map.put('6', "mno");
        map.put('7', "pqrs");
        map.put('8', "tuv");
        map.put('9', "wxyz");
    }

    public static List<String> letterCombinations1(String digits) {
        if (digits == null || digits.length() == 0) {
            return new ArrayList<>();
        }
        List<String> resList = new ArrayList<>();
        backtrace(resList, digits, new StringBuilder(), 0);
        return resList;
    }

    /****
     * 回溯
     * @param resList 结果集合
     * @param digits 拨号数字
     * @param tempRes 临时结果
     * @param index 当前位于哪一个数字
     */
    private static void backtrace(List<String> resList, String digits, StringBuilder tempRes, int index) {
        //数字用完了 那么 临时结果加入到集合
        if (index == digits.length()) {
            resList.add(tempRes.toString());
            return;
        }
        //当前是哪个数字
        char curNum = digits.charAt(index);
        //这个数字对应那些字母
        String allLetter = map.get(curNum);
        //数字的每一个字母都可以用到
        for (int i = 0; i < allLetter.length(); i++) {
            //第1个字母 第二个字母 。。。全部字母用一次
            tempRes.append(allLetter.charAt(i));
            //找下一个数字  树向下
            backtrace(resList, digits, tempRes, index + 1);
            //回溯 回到上一层
            tempRes.deleteCharAt(tempRes.length() - 1);
        }
    }
}
